package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}8:44
 */
public class M3 {//寻找匹配的字符串路径
    public static void main(String[] args) {
        char[][] chars = {  {'A','A'}};
        String word = "AA";
        System.out.println(new M3().exist(chars,word));
    }

//    public boolean exist(char[][] board, String word) {
//        char[] words = word.toCharArray();
//        for(int i = 0; i < board.length; i++) {
//            for(int j = 0; j < board[i].length; j++) {
//                if(dfs(board, words, i, j, 0)) return true;//以每个点为起点的情况
//            }
//        }
//        return false;
//    }
//    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
//        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;//退出条件
//        if(k == word.length - 1) return true;
//        char tmp = board[i][j];
//        board[i][j] = '*';//表示走过的路径
//        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
//                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
//        board[i][j] = tmp;
//        return res;
//    }

    /**
     *
     * @param board
     * @param words
     */
    public boolean exist(char[][] board,String words){
        if (!words.equals("")) {
            char[] word = words.toCharArray();
            for (int i = 0; i < board.length; i++){
                for (int j = 0; j < board[i].length; j++){
                    if (getRoad(board,word,i,j,0)){
                        return true;
                    }
                }
            }
        }else {
            return false;
        }
        return false;
    }

    public boolean getRoad(char[][] board,char[] word,int i,int j, int k){
        //先写回溯条件
        if ( i < 0 || i >= board.length || j < 0 || j >= board[i].length || word[k] != board[i][j]){
            return false;
        }

        if (k == word.length-1){
            return true;
        }

        char temp = board[i][j];
        board[i][j] = '/';//表示走过这个回不去
        boolean result = getRoad(board,word,i+1,j,k+1)
                ||getRoad(board,word,i-1,j,k+1)
                ||getRoad(board,word,i,j+1,k+1)
                ||getRoad(board,word,i,j-1,k+1);
        board[i][j] = temp;//失败或成功都还原原来的状态以免更换起点后无法正常回溯
        return result;
    }
}
